package Sort;

public class QuickSort {
    public static void main(String[] args) {
        int[] a = {3, 6, 1, 3, 9, 5};
        quickSort(a,0,a.length-1);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
    }

    public static void quickSort(int[] a,int left,int right){
        if(left>=right){
            return;
        }
        int i=left,j=right;
        int base=a[left];
        while (i<j){
            while(a[j]>=base&&i<j){
                j--;
            }
            int temp=a[i];
            a[i]=a[j];
            a[j]=temp;
            while(a[i]<=base&&i<j){
                i++;
            }
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;
        }

        quickSort(a,left,i-1);
        quickSort(a,i+1,right);
    }
}

